class Solution {
public:
    int search(vector<int>& nums, int target) {
        //数组：有序+无序 两部分
        
        /*  先判断nums[mid]=?=target,是就返回。否则，说明一定在[begin,mid-1],[mid+1,end]两个区间中

        1. 如果nums[begin]<nums[mid] 说明前半部分 [begin,mid-1]有序
                再去[begin,mid-1] 中寻找  如果target在此区间中，就缩小搜索范围为[begin,mid-1]
                否则就肯定在另一半 [mid,end]中
        2.  如果前半部分无序 那就说明后半部分有序
            同理，去[mid+1,end] 寻找，若在，就将l = mid+1   缩小范围
            否则就肯定在[begin,mid-1]中
        */
        int pos = -1;
        int l = 0,r = nums.size()-1;int mid;
        if (r==0){
            if (nums[0]==target) return 0;
            else return -1;
        }
        while(l<=r){
            mid = (r+l)/2;
            if (nums[mid]==target){
                pos = mid; return pos;
            }
            //说明在两边搜索可以搜到
            if (nums[0]<=nums[mid]){//当前值在前半部分有序中
                if (target>=nums[l]&&target<=nums[mid]){
                    r = mid - 1;
                }else{
                    l = mid + 1;//[mid+1,end]去搜
                }
            }else{
                //在后半部分中
                if (target>=nums[mid]&&target<=nums[nums.size()-1]){
                    l = mid + 1;
                }else{
                    r = mid -1;
                }
            }
        }
        return pos;
    }
};